package basis.netease.hard;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 7-13 最多能完成排序的块
 * 给你一个整数数组 arr 。将 arr 分割成若干 块 ，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
 * 返回能将数组分成的最多块数？
 * 输入格式:
 * 1. 输入整数数列，元素之间以空格分开
 * 2. 其中数组长度为n，1<=n<=1000,
 * 3. 数组元素 1 <= arr[i], k <= 100，数组元素可有重复整数
 * 输出格式:
 * 数组能分成的最多块数
 * 输入样例1:
 * 在这里给出一组输入。例如：
 * 5 4 3 2 1
 * 输出样例1:
 * 在这里给出相应的输出。例如：
 * 1
 * 解释：
 * 将数组分成2块或者更多块，都无法得到所需的结果。
 * 例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。
 * 输入样例2:
 * 在这里给出一组输入。例如：
 * 2 1 3 4 4
 * 输出样例2:
 * 在这里给出相应的输出。例如：
 * 4
 * 解释：
 * 可以把它分成两块，例如 [2, 1], [3, 4, 4]。
 * 然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
 */
public class Main_11 {
    public static void main(String[] args) {
        // 如果每一块升序后再连接的结果和原数组直接升序的结果相同。则说明max(当前块数大小)<=min(下一块数大小)。
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 单调栈（递增）：栈里最终存的是每一块的最大值
        LinkedList<Integer> stack = new LinkedList<>();
        for (int n : arr) {
            // n比栈顶大，先直接入栈
            if (stack.isEmpty() || stack.peek() <= n) {
                stack.push(n);
            } else {
                // n比栈顶小，则说明栈内比n大的值都是和n在同一块，否则无法保证max(当前块数大小)<=min(下一块数大小)。
                // 将所有比n大的数出栈，最后将该块的最大值入栈
                int maxVal = stack.pop();
                while (!stack.isEmpty() && stack.peek() > n) {
                    stack.pop();
                }
                stack.push(maxVal);
            }
        }
        System.out.print(stack.size());
    }

}
